SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Logic optimization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Logic optimization</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="Minimisation_(disambiguation)" class="mw-redirect mw-disambig" title="Minimisation (disambiguation)">Minimisation</a>.</div>

</p><p><b>Logic optimization</b> is a process of finding an equivalent representation of the specified <a href="Logic_circuit" class="mw-redirect" title="Logic circuit">logic circuit</a> under one or more specified constraints. This process is a part of a <a href="Logic_synthesis" title="Logic synthesis">logic synthesis</a> applied in <a href="Digital_electronics" title="Digital electronics">digital electronics</a> and <a href="Integrated_circuit_design" title="Integrated circuit design">integrated circuit design</a>.

</p><p>Generally, the circuit is constrained to a minimum chip area meeting a predefined response delay. The goal of logic optimization of a given circuit is to obtain the smallest <a href="Logic_circuit" class="mw-redirect" title="Logic circuit">logic circuit</a> that evaluates to the same values as the original one.<sup id="cite_ref-Maxfield_2008_1-0" class="reference"><a href="#cite_note-Maxfield_2008-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Usually, the smaller circuit with the same function is cheaper,<sup id="cite_ref-Balasanyan-Aghagulyan-Wuttke-Henke_2018_2-0" class="reference"><a href="#cite_note-Balasanyan-Aghagulyan-Wuttke-Henke_2018-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> takes less space, <a href="Power_efficiency" class="mw-redirect" title="Power efficiency">consumes less power</a>, has shorter latency, and minimizes risks of unexpected <a href="Crosstalk" title="Crosstalk">cross-talk</a>, <a href="Hazard_(logic)" title="Hazard (logic)">hazard of delayed signal processing</a>, and other issues present at the nano-scale level of metallic structures on an <a href="Integrated_circuit" title="Integrated circuit">integrated circuit</a>.

</p><p>In terms of <a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a>, the optimization of a complex <a href="Boolean_expression" title="Boolean expression">Boolean expression</a> is a process of finding a simpler one, which would upon evaluation ultimately produce the same results as the original one.

</p>

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

<p>The problem with having a complicated <a href="Electronic_circuit" title="Electronic circuit">circuit</a> (i.e. one with many elements, such as <a href="Logic_gate" title="Logic gate">logic gates</a>) is that each element takes up physical space and costs time and money to produce. Circuit minimization may be one form of logic optimization used to reduce the area of complex logic in <a href="Integrated_circuit" title="Integrated circuit">integrated circuits</a>.

</p><p>With the advent of <a href="Logic_synthesis" title="Logic synthesis">logic synthesis</a>, one of the biggest challenges faced by the <a href="Electronic_design_automation" title="Electronic design automation">electronic design automation</a> (EDA) industry was to find the most simple circuit representation of the given design description.<sup id="cite_ref-NB_Netlist_3-0" class="reference"><a href="#cite_note-NB_Netlist-3"><span class="cite-bracket">[</span>nb 1<span class="cite-bracket">]</span></a></sup> While <a href="Two-level_logic_optimization" class="mw-redirect" title="Two-level logic optimization">two-level logic optimization</a> had long existed in the form of the <a href="Quine%E2%80%93McCluskey_algorithm" title="Quine–McCluskey algorithm">Quine–McCluskey algorithm</a>, later followed by the <a href="Espresso_heuristic_logic_minimizer" title="Espresso heuristic logic minimizer">Espresso heuristic logic minimizer</a>, the rapidly improving chip densities, and the wide adoption of <a href="Hardware_description_language" title="Hardware description language">Hardware description languages</a> for circuit description, formalized the logic optimization domain as it exists today, including <a href="Logic_Friday" class="mw-redirect" title="Logic Friday">Logic Friday</a> (graphical interface), Minilog, and ESPRESSO-IISOJS (many-valued logic).<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Methods">Methods</h2></div>

<p>The methods of logic circuit simplifications are equally applicable to <a href="#Boolean_expression_minimization">Boolean expression minimization</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Classification">Classification</h3></div>

<p>Today, logic optimization is divided into various categories:

</p>

<dl><dt>Based on circuit representation</dt>

<dd>Two-level logic optimization</dd>

<dd>Multi-level logic optimization</dd></dl>

<dl><dt>Based on circuit characteristics</dt>

<dd>Sequential logic optimization</dd>

<dd>Combinational logic optimization</dd></dl>

<dl><dt>Based on type of execution</dt>

<dd>Graphical optimization methods</dd>

<dd>Tabular optimization methods</dd>

<dd>Algebraic optimization methods</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Graphical_methods">Graphical methods</h3></div>

<p>Graphical methods represent the required logical function by a diagram representing the logic variables and value of the function. By manipulating or inspecting a diagram, much tedious calculation may be eliminated.

Graphical minimization methods for two-level logic include:

</p>

<ul><li><i><a href="Euler_diagram" title="Euler diagram">Euler diagram</a></i> (aka <i>Eulerian circle</i>) (1768) by <a href="Leonhard_P._Euler" class="mw-redirect" title="Leonhard P. Euler">Leonhard P. Euler</a> (1707–1783)</li>

<li><i><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></i> (1880) by <a href="John_Venn" title="John Venn">John Venn</a> (1834–1923)</li>

<li><i><a href="Karnaugh_map" title="Karnaugh map">Karnaugh map</a></i> (1953) by <a href="Maurice_Karnaugh" title="Maurice Karnaugh">Maurice Karnaugh</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Boolean_expression_minimization">Boolean expression minimization</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>The same methods of Boolean expression minimization (simplification) listed below may be applied to the circuit optimization.

</p><p>For the case when the Boolean function is specified by a circuit (that is, we want to find an equivalent circuit of minimum size possible), the unbounded circuit minimization problem was long-conjectured to be <a href="Polynomial_hierarchy" title="Polynomial hierarchy"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{2}^{P}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{2}^{P}}</annotation>

</semantics>

</math></span><img src="./e45acb23af4adb55ad3e2c030392ab86740e9009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.145ex; height:3.176ex;" alt="{\displaystyle \Sigma _{2}^{P}}" loading="lazy"></span>-complete</a> in <a href="Time_complexity" title="Time complexity">time complexity</a>, a result finally proved in 2008,<sup id="cite_ref-Buchfuhrer_2011_5-0" class="reference"><a href="#cite_note-Buchfuhrer_2011-5"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> but there are effective heuristics such as <a href="Karnaugh_map" title="Karnaugh map">Karnaugh maps</a> and the <a href="Quine%E2%80%93McCluskey_algorithm" title="Quine–McCluskey algorithm">Quine–McCluskey algorithm</a> that facilitate the process.

</p><p>Boolean function minimizing methods include:

</p>

<ul><li><a href="Quine%E2%80%93McCluskey_algorithm" title="Quine–McCluskey algorithm">Quine–McCluskey algorithm</a></li>

<li><a href="Petrick's_method" title="Petrick's method">Petrick's method</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Optimal_multi-level_methods">Optimal multi-level methods</h3></div>

<p>Methods that find optimal circuit representations of Boolean functions are often referred to as <i>exact synthesis</i> in the literature. Due to the computational complexity, exact synthesis is tractable only for small Boolean functions. Recent approaches map the optimization problem to a <a href="Satisfiability" title="Satisfiability">Boolean satisfiability</a> problem.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> This allows finding optimal circuit representations using a <a href="SAT_solver" title="SAT solver">SAT solver</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Heuristic_methods">Heuristic methods</h3></div>

<p>A <a href="Heuristic" title="Heuristic">heuristic</a> method uses established rules that solve a practical useful subset of the much larger possible set of problems. The heuristic method may not produce the theoretically optimum solution, but if useful, will provide most of the optimization desired with a minimum of effort. An example of a computer system that uses heuristic methods for logic optimization is the <a href="Espresso_heuristic_logic_minimizer" title="Espresso heuristic logic minimizer">Espresso heuristic logic minimizer</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Two-level_versus_multi-level_representations">Two-level versus multi-level representations</h3></div>

<p>While a two-level circuit representation of circuits strictly refers to the flattened view of the circuit in terms of SOPs (<a href="Sum-of-products" class="mw-redirect" title="Sum-of-products">sum-of-products</a>) — which is more applicable to a <a href="Programmable_logic_array" title="Programmable logic array">PLA</a> implementation of the design — a multi-level representation is a more generic view of the circuit in terms of arbitrarily connected SOPs, POSs (<a href="Product-of-sums" class="mw-redirect" title="Product-of-sums">product-of-sums</a>), factored form etc. Logic optimization algorithms generally work either on the structural (SOPs, factored form) or functional representation (<a href="Binary_decision_diagram" title="Binary decision diagram">binary decision diagrams</a>, <a href="Algebraic_decision_diagram" title="Algebraic decision diagram">algebraic decision diagrams</a>) of the circuit. In sum-of-products (SOP) form, AND gates form the smallest unit and are stitched together using ORs, whereas in product-of-sums (POS) form it is opposite. POS form requires parentheses to group the OR terms together under AND gates, because OR has lower precedence than AND. Both SOP and POS forms translate nicely into circuit logic.

</p><p>If we have two functions <i>F</i><sub>1</sub> and <i>F</i><sub>2</sub>:

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{1}=AB+AC+AD,\,}</annotation>

</semantics>

</math></span><img src="./0b259661e61058239e2c3e0d77cbb806cce39b5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.046ex; height:2.509ex;" alt="{\displaystyle F_{1}=AB+AC+AD,\,}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}=A'B+A'C+A'E.\,}</annotation>

</semantics>

</math></span><img src="./264dccb9e791cf0bcb2871fa14bdeacb623ea867.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.951ex; height:2.843ex;" alt="{\displaystyle F_{2}=A'B+A'C+A'E.\,}" loading="lazy"></span></dd></dl>

<p>The above 2-level representation takes six product terms and 24 transistors in CMOS Rep.

</p><p>A functionally equivalent representation in multilevel can be:

</p>

<p>While the number of levels here is 3, the total number of product terms and literals reduce because of the sharing of the term B + C.

</p><p>Similarly, we distinguish between <a href="Combinational_logic" title="Combinational logic">combinational circuits</a> and <a href="Sequential_logic" title="Sequential logic">sequential circuits</a>. Combinational circuits produce their outputs based only on the current inputs. They can be represented by Boolean <a href="Relation_(mathematics)" title="Relation (mathematics)">relations</a>. Some examples are <a href="Priority_encoder" title="Priority encoder">priority encoders</a>, <a href="Binary_decoder" title="Binary decoder">binary decoders</a>, <a href="Multiplexer" title="Multiplexer">multiplexers</a>, <a href="Demultiplexer" class="mw-redirect" title="Demultiplexer">demultiplexers</a>.

</p><p>Sequential circuits produce their output based on both current and past inputs, depending on a clock signal to distinguish the previous inputs from the current inputs. They can be represented by finite state machines. Some examples are <a href="Flip-flop_(electronics)" title="Flip-flop (electronics)">flip-flops</a> and <a href="Counter_(digital)" title="Counter (digital)">counters</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>While there are many ways to minimize a circuit, this is an example that minimizes (or simplifies) a Boolean function. The Boolean function carried out by the circuit is directly related to the algebraic expression from which the function is implemented.<sup id="cite_ref-Mano_2014_8-0" class="reference"><a href="#cite_note-Mano_2014-8"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

Consider the circuit used to represent <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}">

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}</annotation>

</semantics>

</math></span><img src="./69fd28460d1ccf74b045a0d127c6c628659e659d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.413ex; height:3.176ex;" alt="{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}" loading="lazy"></span>. It is evident that two negations, two conjunctions, and a disjunction are used in this statement. This means that to build the circuit one would need two <a href="Inverter_(logic_gate)" title="Inverter (logic gate)">inverters</a>, two <a href="AND_gate" title="AND gate">AND gates</a>, and an <a href="OR_gate" title="OR gate">OR gate</a>.

</p><p>The circuit can simplified (minimized) by applying laws of <a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a> or using intuition. Since the example states that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is true when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is false and the other way around, one can conclude that this simply means <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\neq B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\neq B}</annotation>

</semantics>

</math></span><img src="./c78362703472ea51edc4614b6b7a7bda8e83131c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.606ex; height:2.676ex;" alt="{\displaystyle A\neq B}" loading="lazy"></span>. In terms of logical gates, <a href="Inequality_(mathematics)" title="Inequality (mathematics)">inequality</a> simply means an <a href="XOR_gate" title="XOR gate">XOR gate</a> (exclusive or). Therefore, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}">

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}</annotation>

</semantics>

</math></span><img src="./3d39fa333783b660186f0b2c8d9d383962db4589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.916ex; height:3.176ex;" alt="{\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}" loading="lazy"></span>. Then the two circuits shown below are equivalent, as can be checked using a <a href="Truth_table" title="Truth table">truth table</a>:

</p>

<th>B

</th></tr>

<tr>

<td>F

</td></tr>

<tr>

<td>T

</td></tr>

<tr>

<td>F

</td></tr>

<tr>

<td>T

</td></tr></tbody></table>

<ul><li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a> (BDD)</li>

<li><a href="Don't_care_condition" class="mw-redirect" title="Don't care condition">Don't care condition</a></li>

<li><a href="Prime_implicant" class="mw-redirect" title="Prime implicant">Prime implicant</a></li>

<li><a href="Circuit_complexity" title="Circuit complexity">Circuit complexity</a> — on estimation of the circuit complexity</li>

<li><a href="Function_composition" title="Function composition">Function composition</a></li>

<li><a href="Function_decomposition" class="mw-redirect" title="Function decomposition">Function decomposition</a></li>

<li><a href="Gate_underutilization" class="mw-redirect" title="Gate underutilization">Gate underutilization</a></li>

<li><a href="Logic_redundancy" title="Logic redundancy">Logic redundancy</a></li>

<li><a href="Harvard_minimizing_chart" class="mw-redirect" title="Harvard minimizing chart">Harvard minimizing chart</a> <a href="https://en.wikiversity.org/wiki/Harvard_chart_method" class="extiw external" title="wikiversity:Harvard chart method">(Wikiversity)</a> <a href="https://en.wikibooks.org/wiki/Harvard_Chart_Method" class="extiw external" title="wikibooks:Harvard Chart Method">(Wikibooks)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-NB_Netlist-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-NB_Netlist_3-0">^</a></b></span> <span class="reference-text">The <a href="Netlist" title="Netlist">netlist</a> size can be used to measure simplicity.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMaxfield2008" class="citation book cs1">Maxfield, Clive "Max" (2008-01-01). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/B9780750689748000053">"Chapter 5: "Traditional" Design Flows"</a>. In Maxfield, Clive "Max" (ed.). <i>FPGAs</i>. Instant Access. Burlington: <a href="Newnes_(publisher)" class="mw-redirect" title="Newnes (publisher)">Newnes</a> / <a href="Elsevier_Inc." class="mw-redirect" title="Elsevier Inc.">Elsevier Inc.</a> pp. <span class="nowrap">75–</span>106. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FB978-0-7506-8974-8.00005-3">10.1016/B978-0-7506-8974-8.00005-3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7506-8974-8</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-10-04</span></span>.</cite></span>

</li>

<li id="cite_note-Balasanyan-Aghagulyan-Wuttke-Henke_2018-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Balasanyan-Aghagulyan-Wuttke-Henke_2018_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBalasanyanAghagulyanWuttkeHenke2018" class="citation web cs1">Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten (2018-05-16). <a rel="nofollow" class="external text" href="https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf">"Digital Electronics"</a> <span class="cs1-format">(PDF)</span>. Bachelor Embedded Systems - Year Group. Tempus. DesIRE. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20211004200546/https://ec.europa.eu/programmes/erasmus-plus/project-result-content/120e4810-0d29-4397-9ad4-b4091c2e3d19/Digital%20Electronics.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2021-10-04<span class="reference-accessdate">. Retrieved <span class="nowrap">2021-10-04</span></span>.</cite> (101 pages)</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFTheobaldNowick1998" class="citation journal cs1">Theobald, M.; Nowick, S. M. (November 1998). <a rel="nofollow" class="external text" href="https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download">"Fast heuristic and exact algorithms for two-level hazard-free logic minimization"</a>. <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>. <b>17</b> (11): <span class="nowrap">1130–</span>1147. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F43.736186">10.1109/43.736186</a>.</cite></span>

</li>

<li id="cite_note-Buchfuhrer_2011-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Buchfuhrer_2011_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBuchfuhrerUmans2011" class="citation journal cs1">Buchfuhrer, David; <a href="Christopher_Umans" class="mw-redirect" title="Christopher Umans">Umans, Christopher</a> (January 2011). <a rel="nofollow" class="external text" href="http://users.cms.caltech.edu/~umans/papers/BU07.pdf">"The complexity of Boolean formula minimization"</a> <span class="cs1-format">(PDF)</span>. <i><a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>. <b>77</b> (1). Computer Science Department, <a href="California_Institute_of_Technology" title="California Institute of Technology">California Institute of Technology</a>, Pasadena, California, USA: <a href="Elsevier_Inc." class="mw-redirect" title="Elsevier Inc.">Elsevier Inc.</a>: <span class="nowrap">142–</span>153. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2010.06.011">10.1016/j.jcss.2010.06.011</a>.</cite> This is an extended version of the conference paper: <cite id="CITEREFBuchfuhrerUmans2008" class="citation book cs1">Buchfuhrer, David; <a href="Christopher_Umans" class="mw-redirect" title="Christopher Umans">Umans, Christopher</a> (2008). "The Complexity of Boolean Formula Minimization". <a rel="nofollow" class="external text" href="http://users.cms.caltech.edu/~umans/papers/BU07.pdf"><i>Proceedings of Automata, Languages and Programming, 35th International Colloquium (ICALP)</i></a> <span class="cs1-format">(PDF)</span>. <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>. Vol. 5125. Berlin / Heidelberg, Germany: <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. pp. <span class="nowrap">24–</span>35. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-70575-8_3">10.1007/978-3-540-70575-8_3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-70574-1</bdi>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2018-01-14<span class="reference-accessdate">. Retrieved <span class="nowrap">2018-01-14</span></span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFHaaswijk" class="citation web cs1">Haaswijk, Winston. <a rel="nofollow" class="external text" href="https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf">"SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism"</a> <span class="cs1-format">(PDF)</span>. <i>EPFL</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2022-12-07</span></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFHaaswijk" class="citation web cs1">Haaswijk, Winston. <a rel="nofollow" class="external text" href="https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf">"SAT-Based Exact Synthesis for Multi-Level Logic Networks"</a> <span class="cs1-format">(PDF)</span>. <i>EPFL</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2022-12-07</span></span>.</cite></span>

</li>

<li id="cite_note-Mano_2014-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Mano_2014_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFManoKime2014" class="citation book cs1">Mano, M. Morris; Kime, Charles R. (2014). <i>Logic and Computer Design Fundamentals</i> (4th new international ed.). <a href="Pearson_Education_Limited" class="mw-redirect" title="Pearson Education Limited">Pearson Education Limited</a>. p. 54. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-292-02468-4</bdi>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFLindNelson1977" class="citation book cs1">Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). <a rel="nofollow" class="external text" href="https://archive.org/details/AnalysisDesignOfSequentialDigitalSystems/"><i>Analysis and Design of Sequential Digital Systems</i></a>. <a href="Macmillan_Press" class="mw-redirect" title="Macmillan Press">Macmillan Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-33319266-4</bdi>.</cite> (146 pages)</li>

<li><cite id="CITEREFDe_Micheli1994" class="citation book cs1"><a href="Giovanni_De_Micheli" title="Giovanni De Micheli">De Micheli, Giovanni</a> (1994). <i>Synthesis and Optimization of Digital Circuits</i>. <a href="McGraw-Hill" class="mw-redirect" title="McGraw-Hill">McGraw-Hill</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07-016333-2</bdi>.</cite> (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)</li>

<li><cite id="CITEREFHachtelSomenzi2006" class="citation book cs1">Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. <i>Logic Synthesis and Verification Algorithms</i>. <a href="Springer_Science_%26_Business_Media" class="mw-redirect" title="Springer Science & Business Media">Springer Science & Business Media</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-31005-3</bdi>.</cite></li>

<li><cite id="CITEREFKohaviJha2009" class="citation book cs1">Kohavi, Zvi; Jha, Niraj K. (2009). "4–6". <i>Switching and Finite Automata Theory</i> (3rd ed.). <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-85748-2</bdi>.</cite></li>

<li><cite id="CITEREFRutenbar" class="citation book cs1">Rutenbar, Rob A. <a rel="nofollow" class="external text" href="https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf"><i>Multi-level minimization, Part I: Models & Methods</i></a> <span class="cs1-format">(PDF)</span> (lecture slides). <a href="Carnegie_Mellon_University" title="Carnegie Mellon University">Carnegie Mellon University</a> (CMU). Lecture 7. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180115125725/https://www.ece.cmu.edu/~ee760/760docs/lec07.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2018-01-15<span class="reference-accessdate">. Retrieved <span class="nowrap">2018-01-15</span></span>;</cite> <cite id="CITEREFRutenbar" class="citation book cs1">Rutenbar, Rob A. <a rel="nofollow" class="external text" href="https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf"><i>Multi-level minimization, Part II: Cube/Cokernel Extract</i></a> <span class="cs1-format">(PDF)</span> (lecture slides). <a href="Carnegie_Mellon_University" title="Carnegie Mellon University">Carnegie Mellon University</a> (CMU). Lecture 8. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180115125733/https://www.ece.cmu.edu/~ee760/760docs/lec08.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2018-01-15<span class="reference-accessdate">. Retrieved <span class="nowrap">2018-01-15</span></span>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Digital_electronics118" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Digital_electronics118" style="font-size:114%;margin:0 4em"><a href="Digital_electronics" title="Digital electronics">Digital electronics</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;"><a href="Electronic_component" title="Electronic component">Components</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Transistor" title="Transistor">Transistor</a></li>

<li><a href="Resistor" title="Resistor">Resistor</a></li>

<li><a href="Inductor" title="Inductor">Inductor</a></li>

<li><a href="Capacitor" title="Capacitor">Capacitor</a></li>

<li><a href="Printed_electronics" title="Printed electronics">Printed electronics</a></li>

<li><a href="Printed_circuit_board" title="Printed circuit board">Printed circuit board</a></li>

<li><a href="Electronic_circuit" title="Electronic circuit">Electronic circuit</a></li>

<li><a href="Memory_cell_(computing)" title="Memory cell (computing)">Memory cell</a></li>

<li><a href="Combinational_logic" title="Combinational logic">Combinational logic</a></li>

<li><a href="Sequential_logic" title="Sequential logic">Sequential logic</a></li>

<li><a href="Logic_gate" title="Logic gate">Logic gate</a></li>

<li><a href="Boolean_circuit" title="Boolean circuit">Boolean circuit</a></li>

<li><a href="Integrated_circuit" title="Integrated circuit">Integrated circuit</a> (IC)</li>

<li><a href="Hybrid_integrated_circuit" title="Hybrid integrated circuit">Hybrid integrated circuit</a> (HIC)</li>

<li><a href="Mixed-signal_integrated_circuit" title="Mixed-signal integrated circuit">Mixed-signal integrated circuit</a></li>

<li><a href="Three-dimensional_integrated_circuit" title="Three-dimensional integrated circuit">Three-dimensional integrated circuit</a> (3D IC)</li>

<li><a href="Emitter-coupled_logic" title="Emitter-coupled logic">Emitter-coupled logic</a> (ECL)</li>

<li><a href="Erasable_programmable_logic_device" class="mw-redirect" title="Erasable programmable logic device">Erasable programmable logic device</a> (EPLD)</li>

<li><a href="Macrocell_array" title="Macrocell array">Macrocell array</a></li>

<li><a href="Programmable_logic_array" title="Programmable logic array">Programmable logic array</a> (PLA)</li>

<li><a href="Programmable_logic_device" title="Programmable logic device">Programmable logic device</a> (PLD)</li>

<li><a href="Programmable_Array_Logic" title="Programmable Array Logic">Programmable Array Logic</a> (PAL)</li>

<li><a href="Generic_Array_Logic" title="Generic Array Logic">Generic Array Logic</a> (GAL)</li>

<li><a href="Complex_programmable_logic_device" title="Complex programmable logic device">Complex programmable logic device</a> (CPLD)</li>

<li><a href="Field-programmable_gate_array" title="Field-programmable gate array">Field-programmable gate array</a> (FPGA)</li>

<li><a href="Field-programmable_object_array" title="Field-programmable object array">Field-programmable object array</a> (FPOA)</li>

<li><a href="Application-specific_integrated_circuit" title="Application-specific integrated circuit">Application-specific integrated circuit</a> (ASIC)</li>

<li><a href="Tensor_Processing_Unit" title="Tensor Processing Unit">Tensor Processing Unit</a> (TPU)</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Theory</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Digital_signal" title="Digital signal">Digital signal</a></li>

<li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Logic_synthesis" title="Logic synthesis">Logic synthesis</a></li>

<li><a href="Logic_in_computer_science" title="Logic in computer science">Logic in computer science</a></li>

<li><a href="Computer_architecture" title="Computer architecture">Computer architecture</a></li>

<li><a href="Digital_signal_(signal_processing)" title="Digital signal (signal processing)">Digital signal</a>

<ul><li><a href="Digital_signal_processing" title="Digital signal processing">Digital signal processing</a></li></ul></li>

<li><a href="Circuit_minimization_for_Boolean_functions" class="mw-redirect" title="Circuit minimization for Boolean functions">Circuit minimization</a></li>

<li><a href="Switching_circuit_theory" title="Switching circuit theory">Switching circuit theory</a></li>

<li><a href="Gate_equivalent" title="Gate equivalent">Gate equivalent</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;"><a href="Electronics_design" class="mw-redirect" title="Electronics design">Design</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Logic_synthesis" title="Logic synthesis">Logic synthesis</a></li>

<li><a href="Place_and_route" title="Place and route">Place and route</a>

<ul><li><a href="Placement_(electronic_design_automation)" title="Placement (electronic design automation)">Placement</a></li>

<li><a href="Routing_(electronic_design_automation)" title="Routing (electronic design automation)">Routing</a></li></ul></li>

<li><a href="Transaction-level_modeling" title="Transaction-level modeling">Transaction-level modeling</a></li>

<li><a href="Register-transfer_level" title="Register-transfer level">Register-transfer level</a>

<ul><li><a href="Hardware_description_language" title="Hardware description language">Hardware description language</a></li>

<li><a href="High-level_synthesis" title="High-level synthesis">High-level synthesis</a></li></ul></li>

<li><a href="Formal_equivalence_checking" title="Formal equivalence checking">Formal equivalence checking</a></li>

<li><a href="Synchronous_circuit" title="Synchronous circuit">Synchronous logic</a></li>

<li><a href="Asynchronous_circuit" title="Asynchronous circuit">Asynchronous logic</a></li>

<li><a href="Finite-state_machine" title="Finite-state machine">Finite-state machine</a>

<ul><li><a href="Hierarchical_state_machine" class="mw-redirect" title="Hierarchical state machine">Hierarchical state machine</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Applications</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Computer_hardware" title="Computer hardware">Computer hardware</a>

<ul><li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul></li>

<li><a href="Digital_audio" title="Digital audio">Digital audio</a>

<ul><li><a href="Digital_radio" title="Digital radio">radio</a></li></ul></li>

<li><a href="Digital_photography" title="Digital photography">Digital photography</a></li>

<li><a href="Telephony#Digital_telephony" title="Telephony">Digital telephone</a></li>

<li><a href="Digital_video" title="Digital video">Digital video</a>

<ul><li><a href="Digital_cinematography" title="Digital cinematography">cinematography</a></li>

<li><a href="Digital_television" title="Digital television">television</a></li></ul></li>

<li><a href="Electronic_literature" title="Electronic literature">Electronic literature</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Design issues</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Metastability_(electronics)" title="Metastability (electronics)">Metastability</a></li>

<li><a href="Runt_pulse" title="Runt pulse">Runt pulse</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-23" href="https://en.wikipedia.org/wiki/?title=Logic_optimization&oldid=1287018147">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>